\documentclass[submission]{FPSAC2017}

\articlenumber{61}
\addbibresource{61_McConville.bib}


\usepackage{lipsum}

\title{Enumerative properties of grid associahedra}

\author{Thomas McConville\thanks{\href{mailto:thomasmcconvillea@gmail.com}{thomasmcconvillea@gmail.com}}} % 

\address{School of Mathematics, Massachusetts Institute of Technology}

\received{\today}

\abstract{Coxeter-Catalan combinatorics places familiar Catalan objects in the context of Coxeter systems. Key examples include triangulations of a polygon, nonnesting partitions, and noncrossing partitions. These objects can be interpreted respectively as clusters of a cluster algebra, antichains in the root poset, and elements of a Coxeter group less than a fixed Coxeter element in the absolute order. In each case, the number of objects in question has a simple formula that depends only on the (finite) Coxeter system from which the objects are defined. A richer enumerative relationship between these objects was conjectured by Chapoton and subsequently proved by several authors. We present a new generalization of these Catalan objects as maximal collections of nonkissing paths in the plane, canonical join representations of elements in the Grid-Tamari order, and the shard intersection order of the Grid-Tamari order. We prove that the nonkissing complex admits a particular fan realization from which one can recover the other structures. We conjecture that this fan is the normal fan of a polytope, called the grid associahedron. Furthermore, we prove that one of the identities among Coxeter-Catalan objects conjectured by Chapoton continues to hold in this setting, and we conjecture that the other identities hold as well.
}

\resume{La combinatoire Coxeter-Catalan place les objets catalans familiers dans le contexte des syst\`{e}mes Coxeter. Les exemples cl\'{e}s incluent les triangulations d'un polygone, les partitions nonnesting et les partitions non crois\'{e}es. Ces objets peuvent \^{e}tre interpr\'{e}t\'{e}s respectivement comme des grappes d'une alg\`{e}bre de grappe, d'antich\`{e}ques dans le poset de racine et d'\'{e}l\'{e}ments d'un groupe de Coxeter inf\'{e}rieur \`{a} un \'{e}l\'{e}ment de Coxeter fixe dans l'ordre absolu. Dans chaque cas, le nombre d'objets en question a une formule simple qui ne d\'{e}pend que du syst\`{e}me (fini) Coxeter \`{a} partir duquel les objets sont d\'{e}finis. Une relation \'{e}num\'{e}rative plus riche entre ces objets a \'{e}t\'{e} conjectur\'{e}e par Chapoton et ensuite prouv\'{e}e par plusieurs auteurs. Nous pr\'{e}sentons une nouvelle g\'{e}n\'{e}ralisation de ces objets catalans en tant que collections maximales de chemins non kissing dans le plan, repr\'{e}sentations canoniques d'\'{e}l\'{e}ments d'assemblage dans l'ordre de Grid-Tamari et l'ordre d'intersection de shard de l'ordre Grid-Tamari. Nous prouvons que le complexe nonkissing admet une r\'{e}alisation particuli\`{e}re du ventilateur \`{a} partir de laquelle on peut r\'{e}cup\'{e}rer les autres structures. Nous conjecturons que ce ventilateur est le ventilateur normal d'un polytope, appel\'{e} l'associa\`{e}dre de grille. En outre, nous prouvons que l'une des identit\'{e}s parmi les objets Coxeter-Catalan conjectur\'{e}s par Chapoton continue \`{a} tenir dans ce cadre, et nous conjecturer que les autres identit\'{e}s tiennent aussi.
}

\keywords{Coxeter group, Catalan number, Associahedron, Tamari lattice, semidistributive lattice}


\usepackage{tikz}
\usetikzlibrary[calc,intersections,through,backgrounds,arrows,decorations.pathmorphing]
\usepackage{mathtools}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{corollary}[theorem]{Corollary}


\def\Acal{\mathcal{A}}
\def\Bcal{\mathcal{B}}
\def\Dcal{\mathcal{D}}
\def\Fcal{\mathcal{F}}
\def\Jcal{\mathcal{J}}
\def\Lcal{\mathcal{L}}
\def\Mcal{\mathcal{M}}
\def\Ncal{\mathcal{N}}
\def\Ocal{\mathcal{O}}
\def\Pcal{\mathcal{P}}
\def\Rcal{\mathcal{R}}
\def\Scal{\mathcal{S}}
\def\Tcal{\mathcal{T}}
\def\Wcal{\mathcal{W}}

\def\Cbb{\mathbb{C}}
\def\Rbb{\mathbb{R}}
\def\Sbb{\mathbb{S}}
\def\Zbb{\mathbb{Z}}

\def\Sfrak{\mathfrak{S}}

\def\ss{\scriptstyle}
\def\ra{\rightarrow}
\def\Ra{\Rightarrow}
\def\ov{\overline}
\def\pr{\prime}
\def\setm{\setminus}
\def\wtil{\widetilde}


\DeclareMathOperator{\Bic}{Bic}
\DeclareMathOperator{\Cat}{Cat}
\DeclareMathOperator{\cg}{cg}
\DeclareMathOperator{\Cov}{Cov}
\DeclareMathOperator{\Int}{Int}
\DeclareMathOperator{\init}{init}
\DeclareMathOperator{\NN}{NN}
\DeclareMathOperator{\NC}{NC}
\DeclareMathOperator{\rk}{rk}
\DeclareMathOperator{\term}{term}
\DeclareMathOperator{\GT}{GT}
\DeclareMathOperator{\Seg}{Seg}

\begin{document}

\maketitle




\section{Introduction}

The \emph{associahedron} is a simple polytope whose faces correspond to partial triangulations of a convex polygon. Many geometric realizations of this polytope are known, each of which gives some unique insights in Catalan combinatorics. One family of realizations developed by Chapoton, Fomin, and Zelevinsky \cite{chapoton.fomin.zelevinsky:2002polytopal} and generalized by Hohlweg and Lange \cite{hohlweg.lange:realizations} is related to the structure of the associahedron as a cluster complex for a type A cluster algebra. Given this connection, Fomin and Zelevinsky \cite{fomin.zelevinsky:2003systems} introduced \emph{generalized associahedra} as polytopes whose boundary complex is combinatorially isomorphic to a cluster complex of finite type. The clusters of a finite type cluster algebra are one of several significant classes of combinatorial objects enumerated by the Coxeter-Catalan numbers, along with nonnesting partitions and noncrossing partitions which are recalled in \cref{sec_cox_tri}.

In \cite{chapoton:2004enumerative} and \cite{chapoton:2006nombre}, Chapoton conjectured some remarkable enumerative coincidences among several Coxeter-Catalan objects, which were proved and extended in \cite{armstrong:2009generalized,athanasiadis:2007some,krattenthaler:2006f,thiel:2014h,tzanaki:2008faces}. To compactly present these conjectures, he introduced three polynomials in two variables known as the \emph{$F$-triangle}, \emph{$H$-triangle}, and \emph{$M$-triangle}, defined in \cref{sec_cox_tri}. These polynomials encode enumerative data corresponding to the cluster complex, nonnesting partitions, and noncrossing partitions, respectively. Chapoton conjectured that these three triangles are equal after a particular substitution of variables. We will refer to this conjecture/theorem as the $F=H=M$ conjecture.


In \cite{chapoton:2015stokes}, Chapoton defined the $F$-triangle and $H$-triangle outside the context of cluster algebras for a complex of quadrangulations of a polygon. This complex of partial quadrangulations was introduced by Baryshnikov \cite{baryshnikov:2001stokes}. It is a polytopal subcomplex of the complex of all quadrangulations, for which the polynomials had been previously defined by Armstrong \cite[Section 5.3]{armstrong:2009generalized}. Surprisingly, the same relationship between the $F$-triangle and $H$-triangle seems to hold as in the Coxeter-Catalan setting, which suggests that there is a wider setting for these polynomials. Using the lattice of noncrossing tree partitions defined in \cite{garver.mcconville:2016oriented}, one can also define an $M$-triangle as well.


In this work, we consider the $F=H=M$ conjecture in a new setting. Our $F$-triangle is defined in terms of the faces of the nonkissing complex introduced by Petersen, Pylyavskyy, and Speyer \cite{petersen.pylyavskyy.speyer:noncrossing} and further studied by Santos, Stump, and Welker \cite{santos.stump.welker:noncrossing}. The \emph{nonkissing complex} $\Delta^{NK}(\lambda)$ is a simplicial complex on some paths along the edges of a Young diagram $\lambda$. We leave the details of its construction to \cref{sec_nonkissing}. When $\lambda$ is a rectangle, this complex may be realized as a regular, unimodular, Gorenstein triangulation of the order polytope on a product of two chains. As a result, it determines a monomial basis for the coordinate ring of the complex Grassmannian, which is distinct from the standard basis. More information on the connection with commutative algebra may be found in \cite{petersen.pylyavskyy.speyer:noncrossing} and \cite{santos.stump.welker:noncrossing}.

After removing cone points, the complex $\Delta^{NK}(\lambda)$ is a polytopal sphere, which is equivalent to the usual associahedron complex when $\lambda$ is a rectangle with 2 rows. Because of the connection to the Grassmannian, this polytopal sphere was named the \emph{Grassmann-associahedron} in \cite{santos.stump.welker:noncrossing} when $\lambda$ is a rectangle. For an arbitrary shape, we refer to a polytopal realization of this complex as the \emph{grid associahedron}. More precisely a grid associahedron is a simple polytope whose facets correspond to boundary paths in $\lambda$ and vertices correspond to facets of $\Delta^{NK}(\lambda)$. A combinatorial construction of this polytope by a sequence of ridge truncations starting from the cube is given in \cite[Section 4]{mcconville:2015lattice}.

In \cref{sec_fan}, we give a fan realization of the grid associahedron, from which one may define the $F$-triangle, $H$-triangle, and $M$-triangle. Restricting to the associahedron case, we recover the usual formulas for the three triangles. Our main result is to prove the $F=H$ identity (\cref{thm_FH}) for grid associahedra. We conjecture that the $F=M$ identity in~\eqref{eqn_H_tri_id} holds as well.

The facets of the nonkissing complex admit a natural partial order called the Grid-Tamari order, which we recall in \cref{sec_tamari}. The Grid-Tamari order is a lattice with some additional structure \cite{mcconville:2015lattice}. One may also define the $H$-triangle and $M$-triangle using this extra lattice structure using the canonical join complex and the lattice-theoretic shard intersection order.



We speculate that the $F=H=M$ identities may exist for a much larger class of simplicial fans than those previously considered. We hope that this work will give some insight into determining which fans admit these identities.

All of the results in this work are stated here without proof. Proofs will appear in the full version.


\section{Coxeter-Catalan triangles}\label{sec_cox_tri}

In this section, we briefly recall some combinatorial structures that arise in Coxeter-Catalan combinatorics. A thorough account on the development of this subject may be found in \cite[Chapter 1]{armstrong:2009generalized}.

Given a rank $r$ Coxeter system $(W,S)$, the facets of the cluster complex, nonnesting partitions, and noncrossing partitions are each enumerated by $W$-Catalan numbers,
$$\Cat(W)=\prod_{i=1}^r\frac{h+d_i}{d_i}$$
where $h$ is the Coxeter number and $d_1,\ldots,d_r$ are the degrees of the fundamental invariants in $\Cbb[x_1,\ldots,x_r]^W$. Each of these objects were originally defined and studied in type $A$ before being extended to other types. We define each of these objects in turn, and describe some additional enumerative relationships among them.

Let $W$ be a finite real reflection group with root system $\Phi$ and simple roots $\Pi$. A root is \emph{almost positive} if it is either positive or the negation of a simple root. The set $\Phi_{\geq -1}$ of almost positive roots is the ground set of a flag simplicial complex $\Delta(W)$ known as the \emph{(root) cluster complex}. The faces of $\Delta(W)$ are collections of pairwise compatible almost positive roots, as defined in \cite{fomin.zelevinsky:2003systems}. If $W$ is of type $A_{n-1}$, then the cluster complex is isomorphic to the boundary complex of the (dual) associahedron.


The $F$-triangle \cite{chapoton:2004enumerative} is the polynomial
$$F(x,y)=\sum_{F\in\Delta(W)}x^{|F\cap\Phi^+|}y^{|F\cap(-\Pi)|}.$$
The usual $f$-polynomial of the cluster complex is equal to $F(t,t)$.

For a crystallographic root system $\Phi$, the \emph{root poset} is defined as the poset $(\Phi^+,\leq)$ of positive roots where $\alpha\leq\beta$ if $\beta-\alpha$ is a nonnegative linear combination of simple roots. Postnikov defined the set $\NN(W)$ of \emph{nonnesting partitions} of $W$ to be the antichains of the root poset. Nonnesting partitions may be used to define the $H$-triangle \cite{chapoton:2006nombre},
$$H(x,y)=\sum_{A\in\NN(W)}x^{|A|}y^{|A\cap\Pi|}.$$

We remark that $H(t,1)$ is the usual $h$-polynomial of the cluster complex, which implies
$$H(t+1,1)=t^rF(1/t,1/t),$$
where $r$ is the rank of $W$. A finer relation is given in~\eqref{eqn_H_tri_id}.

Noncrossing partitions were introduced by Kreweras \cite{kreweras:partitions} as partitions of a finite subset of $\{1,\ldots,n\}$ arranged in clockwise order on a circle such that the convex hulls of any two blocks do not intersect. This was generalized to all types separately by Bessis \cite{bessis:2003dual} and Brady and Watt \cite{brady.watt:2002k} as follows.

A \emph{Coxeter element} $c$ is the product of each simple generator, taken in any order. To each root $\alpha$ in $\Phi$, we may associate a reflection that fixes a hyperplane and swaps $\alpha$ and $-\alpha$. For $w\in W$, we let $l_T(w)$ be the length of the shortest expression for $w$ as a product of reflections. Coxeter elements are maximal in the \emph{absolute order}, the poset on $W$ where $u\leq v$ if $l_T(u)+l_T(u^{-1}v)=l_T(v)$. The \emph{noncrossing partitions} $\NC(W,c)$ are all elements of $W$ in the interval $[1,c]$ in absolute order. To recover the original definition by Kreweras, we let $c$ be the long cycle $(12\ldots n)$, and replace an element $u\in[1,c]$ with the set of cycles that appear in the cycle decomposition of $u$.

The poset of noncrossing partitions is graded by the length function $l_T$. This allows one to define the $M$-triangle \cite{chapoton:2004enumerative} as the polynomial
$$\sum_{u\leq v}\mu(u,v)x^{\rk(v)}y^{\rk(u)},$$
where $\mu(u,v)$ is the M\"obius function. The identities conjectured by Chapoton \cite{chapoton:2004enumerative,chapoton:2006nombre} are as follows.
\begin{equation}\label{eqn_H_tri_id}
H(x+1,y+1) = x^rF\left(\frac{1}{x},\frac{1+(x+1)y}{x}\right) = (1+(x+1)y)^rM\left(\frac{(x+1)y}{(x+1)y+1},\frac{y+1}{y}\right)
\end{equation}

Athanasiadis proved the $F=M$ identity \cite{athanasiadis:2007some} by calculating the M\"obius function in terms of faces of the cluster complex and by identifying the $h$-polynomial of the cluster complex with the rank generating function of the noncrossing partition lattice. Thiel proved the $F=H$ identity \cite{thiel:2014h} in a generalized form due to Armstrong \cite{armstrong:2009generalized} by comparing derivatives of each side and using the previously mentioned formula for the $h$-polynomial of the cluster complex.



\section{Nonkissing complexes}\label{sec_nonkissing}

In this section, we define the nonkissing complex, and recall some results from \cite{mcconville:2015lattice} concerning its structure.

Let $\lambda$ be a finite induced subgraph of the integer lattice. We say a point $(a,b)$ is \emph{west} or \emph{south} of $(c,d)$ if $a<c$ or $b<d$, respectively. North and east are defined similarly. A vertex is an \emph{interior} point if all of its four neighbors are in $\lambda$. Vertices in $\lambda$ not in the interior are called \emph{boundary vertices}. We let $V^o$ be the set of interior vertices and $V$ be the set of all vertices of $\lambda$.


A \emph{boundary path} is a sequence of vertices $(v_0,\ldots,v_l),\ l>0$ such that
\begin{itemize}
\item $v_0$ and $v_l$ are boundary vertices,
\item $v_i$ is an interior vertex for $0<i<l$, and
\item $v_i$ is one step south or east of $v_{i-1}$ for $0<i\leq l$.
\end{itemize}

For the most part, we simply use the word \emph{path} to refer to a boundary path if it causes no confusion. A \emph{segment} is a sequence of interior vertices $(v_0,\ldots,v_l),\ l\geq 0$ such that $v_i$ is immediately south or east of $v_{i-1}$ for all $i$. We refer to this kind of path as a segment since it is a part of a boundary path. We say a segment is \emph{lazy} if it only contains one vertex.

Boundary paths $p$ and $q$ are \emph{kissing along a segment} $s$ if
\begin{itemize}
\item both paths contain $s$,
\item $p$ enters $s$ from the west while $q$ enters from the north, and
\item $p$ leaves $s$ to the south while $q$ leaves to the east.
\end{itemize}
We remark that two paths may kiss along several disjoint segments. If they do not kiss along any segment, we say that $p$ and $q$ are \emph{nonkissing}.

For a simplicial complex $\Delta$, the maximal faces are called \emph{facets}. A complex is \emph{pure} if all of its facets have the same size. If $\Delta$ is pure, then the codimension 1 faces are called \emph{ridges}. The \emph{nonkissing complex} $\Delta^{NK}(\lambda)$ is the simplicial complex on boundary paths supported by $\lambda$ whose faces consist of pairwise nonkissing paths. If $p$ only takes east steps or only takes south steps, we say it is a \emph{horizontal} or \emph{vertical} path, respectively. Horizontal and vertical paths are nonkissing with every other path, so they are cone points in the nonkissing complex. The \emph{reduced nonkissing complex} $\wtil{\Delta}^{NK}(\lambda)$ is the subcomplex of $\Delta^{NK}(\lambda)$ with all horizontal and vertical paths removed. The reduced nonkissing complex is pure of dimension $|V^o|-1$. Furthermore, it is \emph{thin}, which means that every ridge is contained in exactly two facets \cite[Corollary 3.3]{mcconville:2015lattice}.

The reduced nonkissing complex has a facet such that each path consists of a sequence of east steps followed by a sequence of south steps, terminating at the boundary. We will refer to this facet as $F_0$. With this setup, we may define the $F$-triangle for the nonkissing complex as

\begin{equation}\label{eqn_F_tri}
F(x,y)=\sum_{F\in\Delta^{NK}}x^{|F\setm F_0|}y^{|F\cap F_0|}.
\end{equation}

We remark that if the graph $\lambda$ is a disjoint union of subgraphs $\lambda=\lambda_1\sqcup\lambda_2$, then the nonkissing complex for $\lambda$ is equal to the join of $\Delta^{NK}(\lambda_1)$ with $\Delta^{NK}(\lambda_2)$. Hence, we may assume that $\lambda$ is a connected graph. We are most interested in the case where $\lambda$ is a rectangle.

If $\lambda$ is a $2\times(n-2)$ rectangle, then the boundary paths in $\lambda$ that change direction at least once are in bijection with diagonals of a polygon with $n$ vertices. Under this bijection, two paths kiss exactly when their corresponding diagonals cross. Hence, the nonkissing complex $\Delta^{NK}(\lambda)$ is isomorphic to the (dual) associahedron in this case. The distinguished facet $F_0$ corresponds to a triangulation where all diagonals are incident to a common vertex.

If $\lambda$ is a $d\times(n-d)$ rectangle shape, then we may identify boundary paths supported by $\lambda$ with the $d$-element subsets of $\{1,\ldots,n\}$ (except for $\{1,\ldots,d\}$ and $\{n-d+1,\ldots,n\}$) by recording the south steps that the path takes. For example, if $\lambda$ is the $3\times 3$ rectangle with corners $(0,0),(0,3),(3,3),(3,0)$, we may identify the subset $\{1,2,4\}$ with the boundary path $((0,1),\ (1,1),\ (1,0))$. The number of facets of $\Delta^{NK}(\lambda)$ is the multidimensional Catalan number
$$(d(n-d))!\prod_{i=1}^d\frac{(i-1)!}{(n-i)!},$$
which is equal to the number of standard Young tableaux of shape $d\times(n-d)$. This was proved by Santos, Stump, and Welker by realizing $\Delta^{NK}(\lambda)$ as a unimodular triangulation of a polytope. This polytope admits a different unimodular triangulation whose facets are indexed by standard Young tableaux of rectangular shape. No bijective proof is known; see \cite[Open Problem 2.22]{santos.stump.welker:noncrossing} for some desirable properties such a bijection would have.


\section{Grid-Tamari order}\label{sec_tamari}

The facets of the nonkissing complex form a graph where two facets are adjacent if they intersect in a ridge. We orient this graph $F\stackrel{s}{\ra} F^{\pr}$ if $F\setm F^{\pr}=\{p\},\ F^{\pr}\setm F=\{q\}$, and the paths $p,q$ kiss along the segment $s$ such that $q$ enters $s$ from the north and $p$ enters $s$ from the west. \cref{fig_GT36} shows this graph on the 42 facets of the nonkissing complex when $\lambda$ is a $3\times 3$ shape, where all edges are directed upwards. An example facet of $\wtil{\Delta}^{NK}(\lambda)$ is shown to the right of this graph.

Given a facet $F$, let $\Dcal(F)$ be the set of segments $s$ such that there exists $F^{\pr}\stackrel{s}{\ra} F$.

\begin{proposition}\label{prop_Gamma}
The set $\{\Dcal(F):\ F\ \mbox{is a facet of}\ \Delta^{NK}\}$ is the set of faces of a flag simplicial complex on segments.
\end{proposition}

We let $\Gamma(\lambda)$ be the simplicial complex of \cref{prop_Gamma}. The compatibility relation between segments that defines $\Gamma$ is very similar to the nonkissing condition on boundary paths. The only differences occur at the endpoints of the segments.

Given a set of segments $G$, a lazy segment $s\in G$ is \emph{isolated} if no other segment in $G$ contains $s$. For $G\in\Gamma$, let $\epsilon(G)$ be the number of isolated lazy segments, and define the $H$-triangle as

\begin{equation}\label{eqn_H_tri}
H(x,y)=\sum_{G\in\Gamma}x^{|G|}y^{\epsilon(G)}.
\end{equation}


The complex $\Gamma$ may seem somewhat arbitrary. In particular, if $\lambda$ is a $2\times n$ rectangle, the faces of $\Gamma(\lambda)$ do not correspond directly to type $A_{n-1}$ nonnesting partitions. However, there is a simple bijection to type $A_{n-1}$ nonnesting partitions in this case that preserves the $H$-triangle as follows. Label the interior vertices $1,2,\ldots,n-1$. To each $G\in\Gamma$, there is a unique nonnesting partition on $1,\ldots,n$ such that for each arc $(i,j)$ there is a segment that starts at $i$ and a segment that ends at $j-1$, and vice versa. The definition of $\Gamma$ was motivated by a lattice-theoretic construction, described below. 

The directed graph on facets of $\Delta^{NK}$ is acyclic, so it defines a poset where $F\leq F^{\pr}$ if there exists a directed path $F\ra\cdots\ra F^{\pr}$. This poset is known as the \emph{Grid-Tamari order}, as it is equivalent to the usual Tamari order when $\lambda$ is a $2\times(n-2)$ rectangle. The acyclicity of the graph is not obvious. In \cite{mcconville:2015lattice}, the directed graph was shown to be acyclic by identifying it with the Hasse diagram of a lattice. Furthermore, the Grid-Tamari order was shown to carry the additional structure of a semidistributive lattice.

\begin{figure}
\centering
\includegraphics{G36}
\caption{\label{fig_GT36}Grid-Tamari order where $\lambda$ is a $3\times 3$ rectangle}
\end{figure}


Semidistributivity is some weakening of distributivity. In a distributive lattice, every element $x$ has a unique irredundant expression $x=\bigvee_{j\in A}j$ as the join of some subset $A$ of join-irreducible elements. In a \emph{semidistributive} lattice, there may be several such irredundant join-representations of an element, but there is a unique minimal representation called the \emph{canonical join-representation}. Here, we compare two join-representations $x=\bigvee_{j\in A}j=\bigvee_{j\in B}j$ by setting $A\leq B$ if for all $j\in A$, there exists $j^{\pr}\in B$ with $j\leq j^{\pr}$.

The \emph{canonical join complex} is the collection of subsets $A$ of join-irreducibles such that $\bigvee A$ is a canonical join-representation of some element. As the name implies, this complex is an abstract simplicial complex, which was proved to be flag for any semidistributive lattice by Barnard \cite{barnard:2016canonical}. For the Grid-Tamari order, the canonical join complex is isomorphic to the complex $\Gamma(\lambda)$ from \cref{prop_Gamma}.



\section{Fan realization of grid associahedra}\label{sec_fan}

To present the analogue of noncrossing partitions, we realize the nonkissing complex as the face poset of a complete simplicial fan. The ridges of this fan may be grouped together into larger codimension 1 cones called shards. We define the \emph{noncrossing partitions} as the set of intersections of shards. This approach to noncrossing partitions for finite Coxeter systems was previously done by Reading and Speyer using Cambrian fans \cite{reading.speyer:2009fans}.

Let $V^o$ be the set of interior vertices of a shape $\lambda$. For a boundary path $p$, let $g_p$ be the vector in $\Rbb^{V^o}$ such that for $v\in V^o$,
$$g_p(v)=\begin{cases}1\ &\mbox{if }p\mbox{ enters }v\mbox{ from the north and leaves to the east,}\\-1\ &\mbox{if }p\mbox{ enters }v\mbox{ from the west and leaves to the south,}\\0\ &\mbox{otherwise.}\end{cases}$$
Given a face $F$ in $\wtil{\Delta}^{NK}(\lambda)$, let $C(F)$ be the cone generated by $\{g_p:\ p\in F\}$.

\begin{theorem}\label{thm_fan}
The set of cones $\{C(F):\ F\in\wtil{\Delta}^{NK}(\lambda)\}$ is a complete simplicial fan such that $C(F)\cap C(F^{\pr})=C(F\cap F^{\pr})$ for any two faces $F,F^{\pr}$. That is, the incidence relation on cones matches the inclusion relation on faces on the nonkissing complex.
\end{theorem}

We refer to this fan as $\Fcal_{\lambda}$. The rays of $\Fcal_{\lambda}$ correspond to boundary paths. We claim that the ridges match up with segments in a natural way. For a vertex $v\in V^o$, let $\alpha_v$ be the linear functional where $\alpha_v(v)=1$ and $\alpha_v(u)=0$ if $u\in V^o\setm\{v\}$. For each segment $s\in S$, let $\alpha_s\in V^*$ be the linear functional $\alpha_s=\sum_{v\in s}\alpha_v$.

Using the labeling on paths in \cite[Theorem 3.2]{mcconville:2015lattice}, one may show that if $F,F^{\pr}$ are facets such that $F\stackrel{s}{\ra}F^{\pr}$, then $\alpha_s(x)=0$ for $x\in C(F\cap F^{\pr})$ and $\alpha_s(x)\geq 0$ for $x\in C(F^{\pr})$. Hence, the fan $\Fcal_{\lambda}$ contains the Grid-Tamari order as an ordering of its maximal cones where $C^{\pr}$ covers $C$ if $C\cap C^{\pr}$ is a ridge and $C^{\pr}$ is on the ``positive'' side of $C\cap C^{\pr}$. The collection of segments $\Dcal(F)$ from \cref{sec_tamari} may be interpreted as the lower walls of the facet $F$.

Given a ridge $R$, let $[R]$ be the union of ridges supported by the same hyperplane as $R$. We claim that $[R]$ is a (codimension 1) cone. Roughly speaking, this means that ridges supported by the same hyperplane may be found close together. Since each ridge is in the kernel of some $\alpha_s$, we obtain a bijection between cones of the form $[R]$ and segments supported by $\lambda$. Following the language of \cite[Section 8]{reading:lattice}, we refer to the cones $[R]$ as \emph{shards}.

Let $\Wcal$ be the set of shards of $\Fcal_{\lambda}$, and let $\Psi$ be the set of cones that may be expressed as the intersection of a subset of $\Wcal$. The set $\Psi$ ordered by \emph{reverse} inclusion is called the \emph{shard intersection order}. This poset is a lattice that is graded by codimension.

We remark that our construction of the shard intersection order differs somewhat from the usual method, as in \cite{reading.speyer:2009fans}. In that work, Reading and Speyer start with the reflection arrangement of a finite Coxeter system and divide each hyperplane into cones called \emph{shards}. Many of these shards are then removed, revealing a coarser fan known as a \emph{Cambrian fan}. The shard intersection order is defined as the intersections of shards that were not deleted by this coarsening process. Their technique relies on the fact that the poset of regions (see e.g., \cite{bjorner.edelman.ziegler:lattice}) of a reflection arrangement is a lattice. However, the arrangement of hyperplanes $\Acal_{\lambda}$ that support ridges of $\Fcal_{\lambda}$ does not have a lattice of regions whenever $\lambda$ contains a $3\times 3$ square. Fortunately, we may describe the fan $\Fcal_{\lambda}$ directly without starting from $\Acal_{\lambda}$.

For a facet $F$, let $\psi(F)=\cap_{R\in\Dcal(F)}[R]$ be an element of $\Psi$.

\begin{theorem}\label{thm_shards}
The map $\psi$ is a bijection from facets of $\Delta^{NK}$ to the shard intersection order $\Psi$. The inverse $\psi^{-1}$ is order-preserving.
\end{theorem}

Using $\Psi$, we may define the $M$-triangle as
\begin{equation}\label{eqn_M_tri}
M(x,y)=\sum_{\substack{C,D\in\Psi\\C\leq D}}\mu(C,D)x^{\rk(D)}y^{\rk(C)}.
\end{equation}




\section{Enumerative coincidences}\label{sec_enum}

For a fixed shape $\lambda$, we defined the $F$-triangle, $H$-triangle, and $M$-triangle in terms of the nonkissing complex $\Delta^{NK}(\lambda)$~\eqref{eqn_F_tri}, the canonical join complex $\Gamma(\lambda)$~\eqref{eqn_H_tri}, and the shard intersection order $\Psi(\lambda)$~\eqref{eqn_M_tri}. We conjecture that the identities in~\eqref{eqn_H_tri_id} still hold for these triangles. For now, we only claim the $F=H$ identity.

\begin{theorem}\label{thm_FH}
The following identity holds.
$$H(x+1,y+1) = x^rF\left(\frac{1}{x},\frac{1+y(x+1)}{x}\right)$$
\end{theorem}

To prove \cref{thm_FH}, we first define matrices $(f_{ij})_{i,j=0}^r$ and $(h_{ij})_{i,j=0}^r$ where
\begin{align*}
h_{ij} &=|\{F\in\Gamma:\ |F|=j,\ \epsilon(F)=i\}|,\ \mbox{and}\\
f_{ij} &=|\{F\in\Delta^{NK}:\ |F|=j,\ |F\cap F_0|=i\}|.
\end{align*}

In the full version of this work, we prove that the $f$-matrix is equal to the $h$-matrix times an upper triangular matrix $(t_{ij})_{i,j=0}^r$ where $t_{ij}=\binom{r-i}{j-i}$ if $i\leq j$. Using this identity, \cref{thm_FH} reduces to a symmetry of the $H$-triangle, which we prove using an analogue of Kreweras complementation for semidistributive lattices.

We have confirmed the $F=H=M$ conjecture for many small shapes using Sage \cite{sage}. For example, if $\lambda$ is a $3\times 3$ rectangle, the three triangles are the following polynomials.

\begin{align*}
F(x,y) &= \!\begin{multlined}[t]  1 + 10x + 4y + 28x^2 + 22xy + 6y^2 + 30x^3 + 34x^2y + 16xy^2 + 4y^3
 + 11x^4 \\+ 16x^3y + 10x^2y^2 + 4xy^3 + y^4\end{multlined} \\
H(x,y) & = 1 + 6x + 4x^2 + 4xy + 10x^2y + 2x^3y + 6x^2y^2 + 4x^3y^2 + 4x^3y^3 + x^4y^4\\
M(x,y) &= \!\begin{multlined}[t] 1 - 10x + 28x^2 + 10xy - 30x^3 - 48x^2y + 11x^4 + 68x^3y + 20x^2y^2 - 30x^4y\\
 - 48x^3y^2 + 28x^4y^2 + 10x^3y^3 - 10x^4y^3 + x^4y^4\end{multlined}
\end{align*}


\acknowledgements


The author thanks Alexander Garver, as well as Emily Barnard, Christophe Hohlweg, Nathan Reading, and Nathan Williams for helpful discussions.

\printbibliography


\end{document}
